package com.mj.listen2._02_并查集;

/**
 * Quick Union 基于Size的优化
 */
public class UnionFind_QU_S extends UnionFind_QU {

    /**
     * 用于统计某个根节点下面的节点个数size
     */
    private int[] sizes;

    public UnionFind_QU_S(int capacity) {
        super(capacity);
        // size2[0]，根节点0下面的节点size个数
        sizes = new int[capacity];
        // sizes默认所有根节点的数量都是 1。以i为根节点的那颗树节点数量是 1
        for (int i = 0; i < sizes.length; i++) {
            sizes[i] = 1;
        }
    }

    /**
     * 将v1的根节点嫁接到v2的根节点上
     */
    @Override
    public void union(int v1, int v2) {
        // 找到v1的根节点
        int p1 = find(v1);
        // 找到v2的根节点
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }

        if (sizes[p1] < sizes[p2]) {
            // p1根节点下面的节点数量少于p2根节点下面的节点数量。把p1的根节点改成p2的根节点
            parents[p1] = p2;
            // 同时要让最新的p2的节点数量增加p1节点下面节点的数量
            sizes[p2] += sizes[p1];
        } else {
            // p2根节点下面的节点数量少于p1根节点下面的节点数量。把p2的根节点改成p1的根节点
            parents[p2] = p1;
            // 同时要让最新的p1的节点数量增加p2节点下面节点的数量
            sizes[p1] += sizes[p2];
        }
    }
}
